package com.ryujung.linked_list.leetCode_146;

import java.util.HashMap;
import java.util.Map;

// test reset
class LRUCache {
    // 双向链表
    class Node {
        int key;
        int val;
        Node pre;
        Node next;

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private int capacity;
    private Node head = new Node(0, 0);
    private Node tail = new Node(0, 0);
    private final Map<Integer, Node> map = new HashMap<>();

    /**
     * 复习HashMap的一些源码知识点
     */
    private int tableSizeFor(int capacity) {
        /**
         * 100000   c
         * 010000   c>>>1
         * -------  |=  (或，位操作，有1则1，全0则0）
         * 110000   c
         * 001100   c>>>2
         * -------  |=
         * 111100
         * ....    c>>>4 ... c>>>>16;
         * --------
         * 11111...111   全部都是1
         * +         1
         * -------------
         * 10000...000   获得大于c的最小的2的整数次幂 的值
         *
         * 该值将用于简化后续的取余操作   hash % capacity  ->  hash&(capacity -1)
         * 例如：
         * hash值为11010001，也就是209，capacity为1000，也就是8
         * 为了获取该hash值对应在该map中的桶的位置，需要取模
         * 即  hash%capacity，余数为该值对应的桶的位置
         * 209 % 8 = 26 余1
         * 如果使用位运算，就是  hash & (capacity-1)
         * 11010001
         * 00000111
         * ----------
         * 00000001  ，结果为1
         * 原理就是对任意一个数对2^n取余，相当于，取出该值的最低n位的值
         * 209对8(2^3)取余，就是获取209的最低3位的值！！
         *
         * 注意，该方法只对2的整数次幂有效，其他数值不可做这种替换！！
         *
         * 简化该操作的目的： 位运算会比整数的取模操作快一个数量级，就是快很多
         * 也就是便于提高map的索引速度
         */
        capacity = capacity - 1;
        capacity |= capacity >>> 1;
        capacity |= capacity >>> 2;
        capacity |= capacity >>> 4;
        capacity |= capacity >>> 8;
        capacity |= capacity >>> 16;

        return capacity < 0 ? 1 :
                (capacity >= Integer.MAX_VALUE ? Integer.MAX_VALUE : capacity + 1);
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;

        // 在移动到头部前，要先从原有的位置删除，让pre和next相连接（容易犯错，debug了好久...）
        node.pre.next = node.next;
        node.next.pre = node.pre;

        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            // 从链表中取出该节点，修改value
            node.val = value;
            node.pre.next = node.next;
            node.next.pre = node.pre;
        } else {
            node = new Node(key, value);
            map.put(key, node);
        }

        moveToHead(node);
        if (map.size() > capacity) {
            removeTailNode();
        }
    }

    private void removeTailNode() {
        Node preTail = tail.pre;
        if (preTail != head) {
            map.remove(preTail.key);
            preTail.pre.next = tail;
            tail.pre = preTail.pre;
        }
    }

    // 将node移动到链表的首部
    private void moveToHead(Node node) {
        // 将node移动到链表的首部
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    /**
     * 测试用例:["LRUCache","put","put","get","put","get","put","get","get","get"]
     * [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
     * 测试结果:[null,null,null,1,null,2,null,1,3,4]
     * 期望结果:[null,null,null,1,null,-1,null,-1,3,4]
     */
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }

}